home *** CD-ROM | disk | FTP | other *** search
/ isnet Internet / Isnet Internet CD.iso / prog / hiz / 09 / 09.exe / adynware.exe / perl / lib / site / Math / MatrixBool.pm < prev    next >
Encoding:
Perl POD Document  |  1999-12-28  |  46.5 KB  |  1,924 lines
  1.  
  2.  
  3. package Math::MatrixBool;
  4.  
  5. use strict;
  6. use vars qw(@ISA @EXPORT @EXPORT_OK $VERSION);
  7.  
  8. require Exporter;
  9.  
  10. @ISA = qw(Exporter);
  11.  
  12. @EXPORT = qw();
  13.  
  14. @EXPORT_OK = qw();
  15.  
  16. $VERSION = '4.2';
  17.  
  18. use Carp;
  19.  
  20. use Bit::Vector;
  21.  
  22. use overload
  23.      'neg' => '_complement',
  24.        '~' => '_complement',
  25.     'bool' => '_boolean',
  26.        '!' => '_not_boolean',
  27.       '""' => '_string',
  28.      'abs' => '_number_of_elements',
  29.        '+' => '_addition',
  30.        '*' => '_multiplication',
  31.        '|' => '_union',
  32.        '-' => '_difference',
  33.        '&' => '_intersection',
  34.        '^' => '_exclusive_or',
  35.       '+=' => '_assign_addition',
  36.       '*=' => '_assign_multiplication',
  37.       '|=' => '_assign_union',
  38.       '-=' => '_assign_difference',
  39.       '&=' => '_assign_intersection',
  40.       '^=' => '_assign_exclusive_or',
  41.       '==' => '_equal',
  42.       '!=' => '_not_equal',
  43.        '<' => '_true_sub_set',
  44.       '<=' => '_sub_set',
  45.        '>' => '_true_super_set',
  46.       '>=' => '_super_set',
  47.      'cmp' => '_compare',
  48.        '=' => '_clone',
  49. 'fallback' =>   undef;
  50.  
  51. sub new
  52. {
  53.     croak "Usage: \$new_matrix = Math::MatrixBool->new(\$rows,\$columns);"
  54.       if (@_ != 3);
  55.  
  56.     my $proto = shift;
  57.     my $class = ref($proto) || $proto || 'Math::MatrixBool';
  58.     my $rows = shift;
  59.     my $cols = shift;
  60.     my $object;
  61.     my $matrix;
  62.  
  63.     croak "Math::MatrixBool::new(): number of rows must be > 0"
  64.       if ($rows <= 0);
  65.  
  66.     croak "Math::MatrixBool::new(): number of columns must be > 0"
  67.       if ($cols <= 0);
  68.  
  69.     $matrix = Bit::Vector->new($rows * $cols);
  70.     if ((defined $matrix) && ref($matrix) && (${$matrix} != 0))
  71.     {
  72.         $object = [ $matrix, $rows, $cols ];
  73.         bless($object, $class);
  74.         return($object);
  75.     }
  76.     else
  77.     {
  78.         croak
  79.   "Math::MatrixBool::new(): unable to create new 'Math::MatrixBool' object";
  80.     }
  81. }
  82.  
  83. sub new_from_string
  84. {
  85.     croak "Usage: \$new_matrix = Math::MatrixBool->new_from_string(\$string);"
  86.       if (@_ != 2);
  87.  
  88.     my $proto  = shift;
  89.     my $class  = ref($proto) || $proto || 'Math::MatrixBool';
  90.     my $string = shift;
  91.     my($line,$values);
  92.     my($rows,$cols);
  93.     my($row,$col);
  94.     my($warn);
  95.     my($object);
  96.  
  97.     $warn = 0;
  98.     $rows = 0;
  99.     $cols = 0;
  100.     $values = [ ];
  101.     while ($string =~ m!^\s* \[ \s+ ( (?: (?: 0|1 ) \s+ )+ ) \] \s*? \n !x)
  102.     {
  103.         $line = $1;
  104.         $string = $';
  105.         $values->[$rows] = [ ];
  106.         @{$values->[$rows]} = split(' ', $line);
  107.         $col = @{$values->[$rows]};
  108.         if ($col != $cols)
  109.         {
  110.             unless ($cols == 0) { $warn = 1; }
  111.             if ($col > $cols) { $cols = $col; }
  112.         }
  113.         $rows++;
  114.     }
  115.     if ($string !~ m!^\s*$!)
  116.     {
  117.         croak "Math::MatrixBool::new_from_string(): syntax error in input string";
  118.     }
  119.     if ($rows == 0)
  120.     {
  121.         croak "Math::MatrixBool::new_from_string(): empty input string";
  122.     }
  123.     if ($warn)
  124.     {
  125.         warn "Math::MatrixBool::new_from_string(): missing elements will be set to zero!\n";
  126.     }
  127.     $object = Math::MatrixBool::new($class,$rows,$cols);
  128.     for ( $row = 0; $row < $rows; $row++ )
  129.     {
  130.         for ( $col = 0; $col < @{$values->[$row]}; $col++ )
  131.         {
  132.             if ($values->[$row][$col] != 0)
  133.             {
  134.                 $object->[0]->Bit_On( $row * $cols + $col );
  135.             }
  136.         }
  137.     }
  138.     return($object);
  139. }
  140.  
  141. sub Dim  #  Returns dimensions of a matrix
  142. {
  143.     croak "Usage: (\$rows,\$columns) = \$matrix->Dim();"
  144.       if (@_ != 1);
  145.  
  146.     my($matrix) = @_;
  147.  
  148.     return( $matrix->[1], $matrix->[2] );
  149. }
  150.  
  151. sub Empty
  152. {
  153.     croak "Usage: \$matrix->Empty();"
  154.       if (@_ != 1);
  155.  
  156.     my($object) = @_;
  157.  
  158.     $object->[0]->Empty();
  159. }
  160.  
  161. sub Fill
  162. {
  163.     croak "Usage: \$matrix->Fill();"
  164.       if (@_ != 1);
  165.  
  166.     my($object) = @_;
  167.  
  168.     $object->[0]->Fill();
  169. }
  170.  
  171. sub Flip
  172. {
  173.     croak "Usage: \$matrix->Flip();"
  174.       if (@_ != 1);
  175.  
  176.     my($object) = @_;
  177.  
  178.     $object->[0]->Flip();
  179. }
  180.  
  181. sub Zero
  182. {
  183.     croak "Usage: \$matrix->Zero();"
  184.       if (@_ != 1);
  185.  
  186.     my($object) = @_;
  187.  
  188.     $object->[0]->Empty();
  189. }
  190.  
  191. sub One  #  Fills main diagonal
  192. {
  193.     croak "Usage: \$matrix->One();"
  194.       if (@_ != 1);
  195.  
  196.     my($object) = @_;
  197.     my($rows,$cols) = ($object->[1],$object->[2]);
  198.     my($i,$k);
  199.  
  200.     $object->[0]->Empty();
  201.     $k = ($rows <= $cols) ? $rows : $cols;
  202.     for ( $i = 0; $i < $k; $i++ )
  203.     {
  204.         $object->[0]->Bit_On( $i * $cols + $i );
  205.     }
  206. }
  207.  
  208. sub Bit_On
  209. {
  210.     croak "Usage: \$matrix->Bit_On(\$row,\$column);"
  211.       if (@_ != 3);
  212.  
  213.     my($object,$row,$col) = @_;
  214.     my($rows,$cols) = ($object->[1],$object->[2]);
  215.  
  216.     croak "Math::MatrixBool::Bit_On(): row index out of range"
  217.       if (($row < 1) || ($row > $rows));
  218.     croak "Math::MatrixBool::Bit_On(): column index out of range"
  219.       if (($col < 1) || ($col > $cols));
  220.  
  221.     $object->[0]->Bit_On( --$row * $cols + --$col );
  222. }
  223.  
  224. sub Insert
  225. {
  226.     Bit_On(@_);
  227. }
  228.  
  229. sub Bit_Off
  230. {
  231.     croak "Usage: \$matrix->Bit_Off(\$row,\$column);"
  232.       if (@_ != 3);
  233.  
  234.     my($object,$row,$col) = @_;
  235.     my($rows,$cols) = ($object->[1],$object->[2]);
  236.  
  237.     croak "Math::MatrixBool::Bit_Off(): row index out of range"
  238.       if (($row < 1) || ($row > $rows));
  239.     croak "Math::MatrixBool::Bit_Off(): column index out of range"
  240.       if (($col < 1) || ($col > $cols));
  241.  
  242.     $object->[0]->Bit_Off( --$row * $cols + --$col );
  243. }
  244.  
  245. sub Delete
  246. {
  247.     Bit_Off(@_);
  248. }
  249.  
  250. sub bit_flip
  251. {
  252.     croak "Usage: \$boolean = \$matrix->bit_flip(\$row,\$column);"
  253.       if (@_ != 3);
  254.  
  255.     my($object,$row,$col) = @_;
  256.     my($rows,$cols) = ($object->[1],$object->[2]);
  257.  
  258.     croak "Math::MatrixBool::bit_flip(): row index out of range"
  259.       if (($row < 1) || ($row > $rows));
  260.     croak "Math::MatrixBool::bit_flip(): column index out of range"
  261.       if (($col < 1) || ($col > $cols));
  262.  
  263.     return( $object->[0]->bit_flip( --$row * $cols + --$col ) );
  264. }
  265.  
  266. sub flip
  267. {
  268.     return( bit_flip(@_) );
  269. }
  270.  
  271. sub bit_test
  272. {
  273.     croak "Usage: \$boolean = \$matrix->bit_test(\$row,\$column);"
  274.       if (@_ != 3);
  275.  
  276.     my($object,$row,$col) = @_;
  277.     my($rows,$cols) = ($object->[1],$object->[2]);
  278.  
  279.     croak "Math::MatrixBool::bit_test(): row index out of range"
  280.       if (($row < 1) || ($row > $rows));
  281.     croak "Math::MatrixBool::bit_test(): column index out of range"
  282.       if (($col < 1) || ($col > $cols));
  283.  
  284.     return( $object->[0]->bit_test( --$row * $cols + --$col ) );
  285. }
  286.  
  287. sub contains
  288. {
  289.     return( bit_test(@_) );
  290. }
  291.  
  292. sub in
  293. {
  294.     return( bit_test(@_) );
  295. }
  296.  
  297. sub Number_of_elements  #  returns the number of elements which are set
  298. {
  299.     croak "Usage: \$elements = \$matrix->Number_of_elements();"
  300.       if (@_ != 1);
  301.  
  302.     my($object) = @_;
  303.  
  304.     return( $object->[0]->Norm() );
  305. }
  306.  
  307. sub Norm_max  #  Maximum of sums of each row
  308. {
  309.     croak "Usage: \$norm_max = \$matrix->Norm_max();"
  310.       if (@_ != 1);
  311.  
  312.     my($object) = @_;
  313.     my($rows,$cols) = ($object->[1],$object->[2]);
  314.     my($max,$sum,$i,$j);
  315.  
  316.     $max = 0;
  317.     for ( $i = 0; $i < $rows; $i++ )
  318.     {
  319.         $sum = 0;
  320.         for ( $j = 0; $j < $cols; $j++ )
  321.         {
  322.             $sum ^= $object->[0]->bit_test( $i * $cols + $j );
  323.         }
  324.         if ($sum > $max) { $max = $sum; }
  325.     }
  326.     return($max);
  327. }
  328.  
  329. sub Norm_one  #  Maximum of sums of each column
  330. {
  331.     croak "Usage: \$norm_one = \$matrix->Norm_one();"
  332.       if (@_ != 1);
  333.  
  334.     my($object) = @_;
  335.     my($rows,$cols) = ($object->[1],$object->[2]);
  336.     my($max,$sum,$i,$j);
  337.  
  338.     $max = 0;
  339.     for ( $j = 0; $j < $cols; $j++ )
  340.     {
  341.         $sum = 0;
  342.         for ( $i = 0; $i < $rows; $i++ )
  343.         {
  344.             $sum ^= $object->[0]->bit_test( $i * $cols + $j );
  345.         }
  346.         if ($sum > $max) { $max = $sum; }
  347.     }
  348.     return($max);
  349. }
  350.  
  351. sub Addition
  352. {
  353.     croak "Usage: \$matrix1->Addition(\$matrix2,\$matrix3);"
  354.       if (@_ != 3);
  355.  
  356.     my($matrix1,$matrix2,$matrix3) = @_;
  357.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  358.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  359.     my($rows3,$cols3) = ($matrix3->[1],$matrix3->[2]);
  360.  
  361.     if (($rows1 == $rows2) && ($rows1 == $rows3) &&
  362.         ($cols1 == $cols2) && ($cols1 == $cols3))
  363.     {
  364.         $matrix1->[0]->ExclusiveOr($matrix2->[0],$matrix3->[0]);
  365.     }
  366.     else
  367.     {
  368.         croak "Math::MatrixBool::Addition(): matrix size mismatch";
  369.     }
  370. }
  371.  
  372. sub Multiplication
  373. {
  374.     croak "Usage: \$product_matrix = \$matrix1->Multiplication(\$matrix2);"
  375.       if (@_ != 2);
  376.  
  377.     my($matrix1,$matrix2) = @_;
  378.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  379.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  380.     my($result);
  381.  
  382.     if ($cols1 == $rows2)
  383.     {
  384.         $result = $matrix1->new($rows1,$cols2);
  385.         $result->[0]->Multiplication($rows1,$cols2,
  386.                      $matrix1->[0],$rows1,$cols1,
  387.                      $matrix2->[0],$rows2,$cols2);
  388.     }
  389.     else
  390.     {
  391.         croak "Math::MatrixBool::Multiplication(): matrix size mismatch";
  392.     }
  393.     return($result);
  394. }
  395.  
  396. sub Kleene
  397. {
  398.     croak "Usage: \$closure = \$matrix->Kleene();"
  399.       if (@_ != 1);
  400.  
  401.     my($matrix) = @_;
  402.     my($rows,$cols) = ($matrix->[1],$matrix->[2]);
  403.     my($result);
  404.  
  405.     croak "Math::MatrixBool::Kleene(): matrix is not quadratic"
  406.       if ($rows != $cols);
  407.  
  408.     $result = $matrix->new($rows,$cols);
  409.     $result->Copy($matrix);
  410.     $result->[0]->Closure($rows,$cols);
  411.  
  412.     return($result);
  413. }
  414.  
  415. sub Union
  416. {
  417.     croak "Usage: \$matrix1->Union(\$matrix2,\$matrix3);"
  418.       if (@_ != 3);
  419.  
  420.     my($matrix1,$matrix2,$matrix3) = @_;
  421.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  422.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  423.     my($rows3,$cols3) = ($matrix3->[1],$matrix3->[2]);
  424.  
  425.     if (($rows1 == $rows2) && ($rows1 == $rows3) &&
  426.         ($cols1 == $cols2) && ($cols1 == $cols3))
  427.     {
  428.         $matrix1->[0]->Union($matrix2->[0],$matrix3->[0]);
  429.     }
  430.     else
  431.     {
  432.         croak "Math::MatrixBool::Union(): matrix size mismatch";
  433.     }
  434. }
  435.  
  436. sub Intersection
  437. {
  438.     croak "Usage: \$matrix1->Intersection(\$matrix2,\$matrix3);"
  439.       if (@_ != 3);
  440.  
  441.     my($matrix1,$matrix2,$matrix3) = @_;
  442.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  443.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  444.     my($rows3,$cols3) = ($matrix3->[1],$matrix3->[2]);
  445.  
  446.     if (($rows1 == $rows2) && ($rows1 == $rows3) &&
  447.         ($cols1 == $cols2) && ($cols1 == $cols3))
  448.     {
  449.         $matrix1->[0]->Intersection($matrix2->[0],$matrix3->[0]);
  450.     }
  451.     else
  452.     {
  453.         croak "Math::MatrixBool::Intersection(): matrix size mismatch";
  454.     }
  455. }
  456.  
  457. sub Difference
  458. {
  459.     croak "Usage: \$matrix1->Difference(\$matrix2,\$matrix3);"
  460.       if (@_ != 3);
  461.  
  462.     my($matrix1,$matrix2,$matrix3) = @_;
  463.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  464.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  465.     my($rows3,$cols3) = ($matrix3->[1],$matrix3->[2]);
  466.  
  467.     if (($rows1 == $rows2) && ($rows1 == $rows3) &&
  468.         ($cols1 == $cols2) && ($cols1 == $cols3))
  469.     {
  470.         $matrix1->[0]->Difference($matrix2->[0],$matrix3->[0]);
  471.     }
  472.     else
  473.     {
  474.         croak "Math::MatrixBool::Difference(): matrix size mismatch";
  475.     }
  476. }
  477.  
  478. sub ExclusiveOr
  479. {
  480.     croak "Usage: \$matrix1->ExclusiveOr(\$matrix2,\$matrix3);"
  481.       if (@_ != 3);
  482.  
  483.     my($matrix1,$matrix2,$matrix3) = @_;
  484.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  485.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  486.     my($rows3,$cols3) = ($matrix3->[1],$matrix3->[2]);
  487.  
  488.     if (($rows1 == $rows2) && ($rows1 == $rows3) &&
  489.         ($cols1 == $cols2) && ($cols1 == $cols3))
  490.     {
  491.         $matrix1->[0]->ExclusiveOr($matrix2->[0],$matrix3->[0]);
  492.     }
  493.     else
  494.     {
  495.         croak "Math::MatrixBool::ExclusiveOr(): matrix size mismatch";
  496.     }
  497. }
  498.  
  499. sub Complement
  500. {
  501.     croak "Usage: \$matrix1->Complement(\$matrix2);"
  502.       if (@_ != 2);
  503.  
  504.     my($matrix1,$matrix2) = @_;
  505.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  506.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  507.  
  508.     if (($rows1 == $rows2) && ($cols1 == $cols2))
  509.     {
  510.         $matrix1->[0]->Complement($matrix2->[0]);
  511.     }
  512.     else
  513.     {
  514.         croak "Math::MatrixBool::Complement(): matrix size mismatch";
  515.     }
  516. }
  517.  
  518. sub equal
  519. {
  520.     croak "Usage: \$boolean = \$matrix1->equal(\$matrix2);"
  521.       if (@_ != 2);
  522.  
  523.     my($matrix1,$matrix2) = @_;
  524.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  525.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  526.  
  527.     if (($rows1 == $rows2) && ($cols1 == $cols2))
  528.     {
  529.         return( $matrix1->[0]->equal($matrix2->[0]) );
  530.     }
  531.     else
  532.     {
  533.         croak "Math::MatrixBool::equal(): matrix size mismatch";
  534.     }
  535. }
  536.  
  537. sub subset
  538. {
  539.     croak "Usage: \$boolean = \$matrix1->subset(\$matrix2);"
  540.       if (@_ != 2);
  541.  
  542.     my($matrix1,$matrix2) = @_;
  543.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  544.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  545.  
  546.     if (($rows1 == $rows2) && ($cols1 == $cols2))
  547.     {
  548.         return( $matrix1->[0]->subset($matrix2->[0]) );
  549.     }
  550.     else
  551.     {
  552.         croak "Math::MatrixBool::subset(): matrix size mismatch";
  553.     }
  554. }
  555.  
  556. sub inclusion
  557. {
  558.     return( subset(@_) );
  559. }
  560.  
  561. sub lexorder
  562. {
  563.     croak "Usage: \$boolean = \$matrix1->lexorder(\$matrix2);"
  564.       if (@_ != 2);
  565.  
  566.     my($matrix1,$matrix2) = @_;
  567.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  568.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  569.  
  570.     if (($rows1 == $rows2) && ($cols1 == $cols2))
  571.     {
  572.         return( $matrix1->[0]->lexorder($matrix2->[0]) );
  573.     }
  574.     else
  575.     {
  576.         croak "Math::MatrixBool::lexorder(): matrix size mismatch";
  577.     }
  578. }
  579.  
  580. sub Compare
  581. {
  582.     croak "Usage: \$result = \$matrix1->Compare(\$matrix2);"
  583.       if (@_ != 2);
  584.  
  585.     my($matrix1,$matrix2) = @_;
  586.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  587.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  588.  
  589.     if (($rows1 == $rows2) && ($cols1 == $cols2))
  590.     {
  591.         return( $matrix1->[0]->Compare($matrix2->[0]) );
  592.     }
  593.     else
  594.     {
  595.         croak "Math::MatrixBool::Compare(): matrix size mismatch";
  596.     }
  597. }
  598.  
  599. sub Copy
  600. {
  601.     croak "Usage: \$matrix1->Copy(\$matrix2);"
  602.       if (@_ != 2);
  603.  
  604.     my($matrix1,$matrix2) = @_;
  605.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  606.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  607.  
  608.     if (($rows1 == $rows2) && ($cols1 == $cols2))
  609.     {
  610.         $matrix1->[0]->Copy($matrix2->[0]);
  611.     }
  612.     else
  613.     {
  614.         croak "Math::MatrixBool::Copy(): matrix size mismatch";
  615.     }
  616. }
  617.  
  618. sub Shadow
  619. {
  620.     croak "Usage: \$other_matrix = \$some_matrix->Shadow();"
  621.       if (@_ != 1);
  622.  
  623.     my($matrix) = @_;
  624.     my($result);
  625.  
  626.     $result = $matrix->new($matrix->[1],$matrix->[2]);
  627.     return($result);
  628. }
  629.  
  630. sub Clone
  631. {
  632.     croak "Usage: \$twin_matrix = \$some_matrix->Clone();"
  633.       if (@_ != 1);
  634.  
  635.     my($matrix) = @_;
  636.     my($result);
  637.  
  638.     $result = $matrix->new($matrix->[1],$matrix->[2]);
  639.     $result->Copy($matrix);
  640.     return($result);
  641. }
  642.  
  643.  
  644. sub _complement
  645. {
  646.     my($object,$argument,$flag) = @_;
  647.     my($result);
  648.  
  649.     $result = $object->new($object->[1],$object->[2]);
  650.     $result->Complement($object);
  651.     return($result);
  652. }
  653.  
  654. sub _boolean
  655. {
  656.     my($object,$argument,$flag) = @_;
  657.  
  658.     return( $object->[0]->Min() < $object->[1] * $object->[2] );
  659. }
  660.  
  661. sub _not_boolean
  662. {
  663.     my($object,$argument,$flag) = @_;
  664.  
  665.     return( !($object->[0]->Min() < $object->[1] * $object->[2]) );
  666. }
  667.  
  668. sub _string
  669. {
  670.     my($object,$argument,$flag) = @_;
  671.     my($rows,$cols) = ($object->[1],$object->[2]);
  672.     my($i,$j,$s);
  673.  
  674.     $s = '';
  675.     for ( $i = 1; $i <= $rows; $i++ )
  676.     {
  677.         $s .= "[ ";
  678.         for ( $j = 1; $j <= $cols; $j++ )
  679.         {
  680.             if ($object->bit_test($i,$j)) { $s .= "1 "; } else { $s .= "0 "; }
  681.         }
  682.         $s .= "]\n";
  683.     }
  684.     return($s);
  685. }
  686.  
  687. sub _number_of_elements
  688. {
  689.     my($object,$argument,$flag) = @_;
  690.  
  691.     return( $object->Number_of_elements() );
  692. }
  693.  
  694. sub _addition
  695. {
  696.     my($object,$argument,$flag) = @_;
  697.     my($name) = "'+'"; #&_trace($name,$object,$argument,$flag);
  698.     my($result);
  699.  
  700.     if ((defined $argument) && ref($argument) &&
  701.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  702.     {
  703.         if (defined $flag)
  704.         {
  705.             $result = $object->new($object->[1],$object->[2]);
  706.             $result->ExclusiveOr($object,$argument);
  707.             return($result);
  708.         }
  709.         else
  710.         {
  711.             $object->ExclusiveOr($object,$argument);
  712.             return($object);
  713.         }
  714.     }
  715.     else
  716.     {
  717.         croak "Math::MatrixBool $name: wrong argument type";
  718.     }
  719. }
  720.  
  721. sub _multiplication
  722. {
  723.     my($object,$argument,$flag) = @_;
  724.     my($name) = "'*'"; #&_trace($name,$object,$argument,$flag);
  725.     my($result);
  726.  
  727.     if ((defined $argument) && ref($argument) &&
  728.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  729.     {
  730.         if ((defined $flag) && $flag)
  731.         {
  732.             return( Multiplication($argument,$object) );
  733.         }
  734.         else
  735.         {
  736.             return( Multiplication($object,$argument) );
  737.         }
  738.     }
  739.     else
  740.     {
  741.         croak "Math::MatrixBool $name: wrong argument type";
  742.     }
  743. }
  744.  
  745. sub _union
  746. {
  747.     my($object,$argument,$flag) = @_;
  748.     my($name) = "'|'"; #&_trace($name,$object,$argument,$flag);
  749.     my($result);
  750.  
  751.     if ((defined $argument) && ref($argument) &&
  752.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  753.     {
  754.         if (defined $flag)
  755.         {
  756.             $result = $object->new($object->[1],$object->[2]);
  757.             $result->Union($object,$argument);
  758.             return($result);
  759.         }
  760.         else
  761.         {
  762.             $object->Union($object,$argument);
  763.             return($object);
  764.         }
  765.     }
  766.     else
  767.     {
  768.         croak "Math::MatrixBool $name: wrong argument type";
  769.     }
  770. }
  771.  
  772. sub _difference
  773. {
  774.     my($object,$argument,$flag) = @_;
  775.     my($name) = "'-'"; #&_trace($name,$object,$argument,$flag);
  776.     my($result);
  777.  
  778.     if ((defined $argument) && ref($argument) &&
  779.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  780.     {
  781.         if (defined $flag)
  782.         {
  783.             $result = $object->new($object->[1],$object->[2]);
  784.             if ($flag) { $result->Difference($argument,$object); }
  785.             else       { $result->Difference($object,$argument); }
  786.             return($result);
  787.         }
  788.         else
  789.         {
  790.             $object->Difference($object,$argument);
  791.             return($object);
  792.         }
  793.     }
  794.     else
  795.     {
  796.         croak "Math::MatrixBool $name: wrong argument type";
  797.     }
  798. }
  799.  
  800. sub _intersection
  801. {
  802.     my($object,$argument,$flag) = @_;
  803.     my($name) = "'&'"; #&_trace($name,$object,$argument,$flag);
  804.     my($result);
  805.  
  806.     if ((defined $argument) && ref($argument) &&
  807.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  808.     {
  809.         if (defined $flag)
  810.         {
  811.             $result = $object->new($object->[1],$object->[2]);
  812.             $result->Intersection($object,$argument);
  813.             return($result);
  814.         }
  815.         else
  816.         {
  817.             $object->Intersection($object,$argument);
  818.             return($object);
  819.         }
  820.     }
  821.     else
  822.     {
  823.         croak "Math::MatrixBool $name: wrong argument type";
  824.     }
  825. }
  826.  
  827. sub _exclusive_or
  828. {
  829.     my($object,$argument,$flag) = @_;
  830.     my($name) = "'^'"; #&_trace($name,$object,$argument,$flag);
  831.     my($result);
  832.  
  833.     if ((defined $argument) && ref($argument) &&
  834.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  835.     {
  836.         if (defined $flag)
  837.         {
  838.             $result = $object->new($object->[1],$object->[2]);
  839.             $result->ExclusiveOr($object,$argument);
  840.             return($result);
  841.         }
  842.         else
  843.         {
  844.             $object->ExclusiveOr($object,$argument);
  845.             return($object);
  846.         }
  847.     }
  848.     else
  849.     {
  850.         croak "Math::MatrixBool $name: wrong argument type";
  851.     }
  852. }
  853.  
  854. sub _assign_addition
  855. {
  856.     my($object,$argument,$flag) = @_;
  857.  
  858.     return( &_addition($object,$argument,undef) );
  859. }
  860.  
  861. sub _assign_multiplication
  862. {
  863.     my($object,$argument,$flag) = @_;
  864.  
  865.     return( &_multiplication($object,$argument,undef) );
  866. }
  867.  
  868. sub _assign_union
  869. {
  870.     my($object,$argument,$flag) = @_;
  871.  
  872.     return( &_union($object,$argument,undef) );
  873. }
  874.  
  875. sub _assign_difference
  876. {
  877.     my($object,$argument,$flag) = @_;
  878.  
  879.     return( &_difference($object,$argument,undef) );
  880. }
  881.  
  882. sub _assign_intersection
  883. {
  884.     my($object,$argument,$flag) = @_;
  885.  
  886.     return( &_intersection($object,$argument,undef) );
  887. }
  888.  
  889. sub _assign_exclusive_or
  890. {
  891.     my($object,$argument,$flag) = @_;
  892.  
  893.     return( &_exclusive_or($object,$argument,undef) );
  894. }
  895.  
  896. sub _equal
  897. {
  898.     my($object,$argument,$flag) = @_;
  899.     my($name) = "'=='"; #&_trace($name,$object,$argument,$flag);
  900.  
  901.     if ((defined $argument) && ref($argument) &&
  902.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  903.     {
  904.         return( $object->equal($argument) );
  905.     }
  906.     else
  907.     {
  908.         croak "Math::MatrixBool $name: wrong argument type";
  909.     }
  910. }
  911.  
  912. sub _not_equal
  913. {
  914.     my($object,$argument,$flag) = @_;
  915.     my($name) = "'!='"; #&_trace($name,$object,$argument,$flag);
  916.  
  917.     if ((defined $argument) && ref($argument) &&
  918.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  919.     {
  920.         return( !($object->equal($argument)) );
  921.     }
  922.     else
  923.     {
  924.         croak "Math::MatrixBool $name: wrong argument type";
  925.     }
  926. }
  927.  
  928. sub _true_sub_set
  929. {
  930.     my($object,$argument,$flag) = @_;
  931.     my($name) = "'<'"; #&_trace($name,$object,$argument,$flag);
  932.  
  933.     if ((defined $argument) && ref($argument) &&
  934.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  935.     {
  936.         if ((defined $flag) && $flag)
  937.         {
  938.             return( !($argument->equal($object)) &&
  939.                      ($argument->subset($object)) );
  940.         }
  941.         else
  942.         {
  943.             return( !($object->equal($argument)) &&
  944.                      ($object->subset($argument)) );
  945.         }
  946.     }
  947.     else
  948.     {
  949.         croak "Math::MatrixBool $name: wrong argument type";
  950.     }
  951. }
  952.  
  953. sub _sub_set
  954. {
  955.     my($object,$argument,$flag) = @_;
  956.     my($name) = "'<='"; #&_trace($name,$object,$argument,$flag);
  957.  
  958.     if ((defined $argument) && ref($argument) &&
  959.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  960.     {
  961.         if ((defined $flag) && $flag)
  962.         {
  963.             return( $argument->subset($object) );
  964.         }
  965.         else
  966.         {
  967.             return( $object->subset($argument) );
  968.         }
  969.     }
  970.     else
  971.     {
  972.         croak "Math::MatrixBool $name: wrong argument type";
  973.     }
  974. }
  975.  
  976. sub _true_super_set
  977. {
  978.     my($object,$argument,$flag) = @_;
  979.     my($name) = "'>'"; #&_trace($name,$object,$argument,$flag);
  980.  
  981.     if ((defined $argument) && ref($argument) &&
  982.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  983.     {
  984.         if ((defined $flag) && $flag)
  985.         {
  986.             return( !($object->equal($argument)) &&
  987.                      ($object->subset($argument)) );
  988.         }
  989.         else
  990.         {
  991.             return( !($argument->equal($object)) &&
  992.                      ($argument->subset($object)) );
  993.         }
  994.     }
  995.     else
  996.     {
  997.         croak "Math::MatrixBool $name: wrong argument type";
  998.     }
  999. }
  1000.  
  1001. sub _super_set
  1002. {
  1003.     my($object,$argument,$flag) = @_;
  1004.     my($name) = "'>='"; #&_trace($name,$object,$argument,$flag);
  1005.  
  1006.     if ((defined $argument) && ref($argument) &&
  1007.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  1008.     {
  1009.         if ((defined $flag) && $flag)
  1010.         {
  1011.             return( $object->subset($argument) );
  1012.         }
  1013.         else
  1014.         {
  1015.             return( $argument->subset($object) );
  1016.         }
  1017.     }
  1018.     else
  1019.     {
  1020.         croak "Math::MatrixBool $name: wrong argument type";
  1021.     }
  1022. }
  1023.  
  1024. sub _compare
  1025. {
  1026.     my($object,$argument,$flag) = @_;
  1027.     my($name) = "cmp"; #&_trace($name,$object,$argument,$flag);
  1028.  
  1029.     if ((defined $argument) && ref($argument) &&
  1030.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  1031.     {
  1032.         if ((defined $flag) && $flag)
  1033.         {
  1034.             return( $argument->Compare($object) );
  1035.         }
  1036.         else
  1037.         {
  1038.             return( $object->Compare($argument) );
  1039.         }
  1040.     }
  1041.     else
  1042.     {
  1043.         croak "Math::MatrixBool $name: wrong argument type";
  1044.     }
  1045. }
  1046.  
  1047. sub _clone
  1048. {
  1049.     my($object,$argument,$flag) = @_;
  1050.     my($result);
  1051.  
  1052.     $result = $object->new($object->[1],$object->[2]);
  1053.     $result->Copy($object);
  1054.     return($result);
  1055. }
  1056.  
  1057. sub _trace
  1058. {
  1059.     my($text,$object,$argument,$flag) = @_;
  1060.  
  1061.     unless (defined $object)   { $object   = 'undef'; };
  1062.     unless (defined $argument) { $argument = 'undef'; };
  1063.     unless (defined $flag)     { $flag     = 'undef'; };
  1064.     if (ref($object))   { $object   = ref($object);   }
  1065.     if (ref($argument)) { $argument = ref($argument); }
  1066.     print "$text: \$obj='$object' \$arg='$argument' \$flag='$flag'\n";
  1067. }
  1068.  
  1069. 1;
  1070.  
  1071. __END__
  1072.  
  1073. =head1 NAME
  1074.  
  1075. Math::MatrixBool - Matrix of Booleans
  1076.  
  1077. Easy manipulation of matrices of booleans (Boolean Algebra)
  1078.  
  1079. =head1 SYNOPSIS
  1080.  
  1081. =over 4
  1082.  
  1083. =item *
  1084.  
  1085. C<use Math::MatrixBool;>
  1086.  
  1087. =item *
  1088.  
  1089. C<$new_matrix = new Math::MatrixBool($rows,$columns);>
  1090.  
  1091. the matrix object constructor method
  1092.  
  1093. An exception is raised if the necessary memory cannot be allocated.
  1094.  
  1095. =item *
  1096.  
  1097. C<$new_matrix = Math::MatrixBool-E<gt>new($rows,$columns);>
  1098.  
  1099. alternate way of calling the matrix object constructor method
  1100.  
  1101. =item *
  1102.  
  1103. C<$new_matrix = $some_matrix-E<gt>>C<new($rows,$columns);>
  1104.  
  1105. still another way of calling the matrix object constructor method
  1106. ($some_matrix is not affected by this)
  1107.  
  1108. =item *
  1109.  
  1110. C<$new_matrix = Math::MatrixBool-E<gt>>C<new_from_string($string);>
  1111.  
  1112. This method allows you to read in a matrix from a string (for
  1113. instance, from the keyboard, from a file or from your code).
  1114.  
  1115. The syntax is simple: each row must start with "C<[ >" and end with
  1116. "C< ]\n>" ("C<\n>" being the newline character and "C< >" a space or
  1117. tab) and contain one or more numbers, all separated from each other
  1118. by spaces or tabs.
  1119.  
  1120. Additional spaces or tabs can be added at will, but no comments.
  1121.  
  1122. Numbers are either "0" or "1".
  1123.  
  1124. Examples:
  1125.  
  1126.     $string = "[ 1 0 0 ]\n[ 1 1 0 ]\n[ 1 1 1 ]\n";
  1127.     $matrix = Math::MatrixBool->new_from_string($string);
  1128.     print "$matrix";
  1129.  
  1130. By the way, this prints
  1131.  
  1132.     [ 1 0 0 ]
  1133.     [ 1 1 0 ]
  1134.     [ 1 1 1 ]
  1135.  
  1136. But you can also do this in a much more comfortable way using the
  1137. shell-like "here-document" syntax:
  1138.  
  1139.     $matrix = Math::MatrixBool->new_from_string(<<'MATRIX');
  1140.     [  1  0  0  0  0  0  1  ]
  1141.     [  0  1  0  0  0  0  0  ]
  1142.     [  0  0  1  0  0  0  0  ]
  1143.     [  0  0  0  1  0  0  0  ]
  1144.     [  0  0  0  0  1  0  0  ]
  1145.     [  0  0  0  0  0  1  0  ]
  1146.     [  1  0  0  0  0  0  1  ]
  1147.     MATRIX
  1148.  
  1149. You can even use variables in the matrix:
  1150.  
  1151.     $c1  =  $A1 * $x1 - $b1 >= 0  ?"1":"0";
  1152.     $c1  =  $A2 * $x2 - $b2 >= 0  ?"1":"0";
  1153.     $c1  =  $A3 * $x3 - $b3 >= 0  ?"1":"0";
  1154.  
  1155.     $matrix = Math::MatrixBool->new_from_string(<<"MATRIX");
  1156.  
  1157.         [   1    0    0   ]
  1158.         [   0    1    0   ]
  1159.         [  $c1  $c2  $c3  ]
  1160.  
  1161.     MATRIX
  1162.  
  1163. (Remember that you may use spaces and tabs to format the matrix to
  1164. your taste)
  1165.  
  1166. Note that this method uses exactly the same representation for a
  1167. matrix as the "stringify" operator "": this means that you can convert
  1168. any matrix into a string with C<$string = "$matrix";> and read it back
  1169. in later (for instance from a file!).
  1170.  
  1171. If the string you supply (or someone else supplies) does not obey
  1172. the syntax mentioned above, an exception is raised, which can be
  1173. caught by "eval" as follows:
  1174.  
  1175.     print "Please enter your matrix (in one line): ";
  1176.     $string = <STDIN>;
  1177.     $string =~ s/\\n/\n/g;
  1178.     eval { $matrix = Math::MatrixBool->new_from_string($string); };
  1179.     if ($@)
  1180.     {
  1181.         print "$@";
  1182.     }
  1183.     else
  1184.     {
  1185.     }
  1186.  
  1187. or as follows:
  1188.  
  1189.     eval { $matrix = Math::MatrixBool->new_from_string(<<"MATRIX"); };
  1190.     [   1    0    0   ]
  1191.     [   0    1    0   ]
  1192.     [  $c1  $c2  $c3  ]
  1193.     MATRIX
  1194.     if ($@)
  1195.  
  1196. Actually, the method shown above for reading a matrix from the keyboard
  1197. is a little awkward, since you have to enter a lot of "\n"'s for the
  1198. newlines.
  1199.  
  1200. A better way is shown in this piece of code:
  1201.  
  1202.   while (1)
  1203.   {
  1204.       print "\nPlease enter your matrix ";
  1205.       print "(multiple lines, <ctrl-D> = done):\n";
  1206.       eval { $new_matrix =
  1207.           Math::MatrixBool->new_from_string(join('',<STDIN>)); };
  1208.       if ($@)
  1209.       {
  1210.           $@ =~ s/\s+at\b.*?$//;
  1211.           print "${@}Please try again.\n";
  1212.       }
  1213.       else { last; }
  1214.   }
  1215.  
  1216. Possible error messages of the "new_from_string()" method are:
  1217.  
  1218.     Math::MatrixBool::new_from_string(): syntax error in input string
  1219.     Math::MatrixBool::new_from_string(): empty input string
  1220.  
  1221. If the input string has rows with varying numbers of columns,
  1222. the following warning will be printed to STDERR:
  1223.  
  1224.     Math::MatrixBool::new_from_string(): missing elements will be set to zero!
  1225.  
  1226. If everything is okay, the method returns an object reference to the
  1227. (newly allocated) matrix containing the elements you specified.
  1228.  
  1229. =item *
  1230.  
  1231. C<($rows,$columns) = $matrix-E<gt>Dim();>
  1232.  
  1233. returns the dimensions (= number of rows and columns) of the given matrix
  1234.  
  1235. =item *
  1236.  
  1237. C<$matrix-E<gt>Empty();>
  1238.  
  1239. sets all elements in the matrix to "0"
  1240.  
  1241. =item *
  1242.  
  1243. C<$matrix-E<gt>Fill();>
  1244.  
  1245. sets all elements in the matrix to "1"
  1246.  
  1247. =item *
  1248.  
  1249. C<$matrix-E<gt>Flip();>
  1250.  
  1251. flips (i.e., complements) all elements in the given matrix
  1252.  
  1253. =item *
  1254.  
  1255. C<$matrix-E<gt>Zero();>
  1256.  
  1257. sets all elements in the matrix to "0"
  1258.  
  1259. =item *
  1260.  
  1261. C<$matrix-E<gt>One();>
  1262.  
  1263. fills the matrix with one's in the main diagonal and zero's elsewhere
  1264.  
  1265. Note that multiplying this matrix with itself yields the same matrix again
  1266. (provided it is quadratic)!
  1267.  
  1268. =item *
  1269.  
  1270. C<$matrix-E<gt>Bit_On($row,$column);>
  1271.  
  1272. sets a given element to "1"
  1273.  
  1274. =item *
  1275.  
  1276. C<$matrix-E<gt>Insert($row,$column);>
  1277.  
  1278. alias for "Bit_On()", deprecated
  1279.  
  1280. =item *
  1281.  
  1282. C<$matrix-E<gt>Bit_Off($row,$column);>
  1283.  
  1284. sets a given element to "0"
  1285.  
  1286. =item *
  1287.  
  1288. C<$matrix-E<gt>Delete($row,$column);>
  1289.  
  1290. alias for "Bit_Off()", deprecated
  1291.  
  1292. =item *
  1293.  
  1294. C<$boolean = $matrix-E<gt>>C<bit_flip($row,$column);>
  1295.  
  1296. flips (i.e., complements) a given element and returns its new value
  1297.  
  1298. =item *
  1299.  
  1300. C<$boolean = $matrix-E<gt>>C<flip($row,$column);>
  1301.  
  1302. alias for "bit_flip()", deprecated
  1303.  
  1304. =item *
  1305.  
  1306. C<$boolean = $matrix-E<gt>>C<bit_test($row,$column);>
  1307.  
  1308. tests wether a given element is set
  1309.  
  1310. =item *
  1311.  
  1312. C<$boolean = $matrix-E<gt>>C<contains($row,$column);>
  1313.  
  1314. tests wether a given element is set (alias for "bit_test()")
  1315.  
  1316. =item *
  1317.  
  1318. C<$boolean = $matrix-E<gt>>C<in($row,$column);>
  1319.  
  1320. alias for "bit_test()", deprecated
  1321.  
  1322. =item *
  1323.  
  1324. C<$elements = $matrix-E<gt>Number_of_elements();>
  1325.  
  1326. calculates the number of elements contained in the given matrix
  1327.  
  1328. =item *
  1329.  
  1330. C<$norm_max = $matrix-E<gt>Norm_max();>
  1331.  
  1332. calculates the "maximum"-norm of the given matrix
  1333.  
  1334. =item *
  1335.  
  1336. C<$norm_one = $matrix-E<gt>Norm_one();>
  1337.  
  1338. calculates the "1"-norm of the given matrix
  1339.  
  1340. =item *
  1341.  
  1342. C<$matrix1-E<gt>Addition($matrix2,$matrix3);>
  1343.  
  1344. calculates the sum of matrix2 and matrix3 and stores the result in matrix1
  1345. (in-place is also possible)
  1346.  
  1347. =item *
  1348.  
  1349. C<$product_matrix = $matrix1-E<gt>Multiplication($matrix2);>
  1350.  
  1351. calculates the product of matrix1 and matrix2 and returns an object reference
  1352. to a new matrix where the result is stored
  1353.  
  1354. =item *
  1355.  
  1356. C<$closure = $matrix-E<gt>Kleene();>
  1357.  
  1358. computes the reflexive transitive closure of the given matrix and returns
  1359. a new matrix containing the result. (The original matrix is not changed by
  1360. this in any way!)
  1361.  
  1362. Uses a variant of Kleene's algorithm. See L<Math::Kleene(3)> for more details
  1363. about this algorithm!
  1364.  
  1365. This algorithm is mainly used in graph theory: Each position in the matrix
  1366. corresponds to a (directed!) possible connection ("edge") between two points
  1367. ("vortices") of a graph. Each position in the matrix contains a "1" if the
  1368. corresponding edge is part of the graph and a "0" if not.
  1369.  
  1370. Computing the closure of this matrix means to find out if there is a path
  1371. from any vortice of the graph to any other (a path consisting of one or more
  1372. edges).
  1373.  
  1374. Note that there are more applications of Kleene's algorithm in other fields
  1375. as well (see also Math::MatrixReal(3), DFA::Kleene(3), Math::Kleene(3)).
  1376.  
  1377. =item *
  1378.  
  1379. C<$matrix1-E<gt>Union($matrix2,$matrix3);>
  1380.  
  1381. calculates the union of matrix2 and matrix3 and stores the result in matrix1
  1382. (in-place is also possible)
  1383.  
  1384. =item *
  1385.  
  1386. C<$matrix1-E<gt>Intersection($matrix2,$matrix3);>
  1387.  
  1388. calculates the intersection of matrix2 and matrix3 and stores the result in
  1389. matrix1 (in-place is also possible)
  1390.  
  1391. =item *
  1392.  
  1393. C<$matrix1-E<gt>Difference($matrix2,$matrix3);>
  1394.  
  1395. calculates matrix2 "minus" matrix3 ( = matrix2 \ matrix3 ) and stores the
  1396. result in matrix1 (in-place is also possible)
  1397.  
  1398. Note that this is set difference, not matrix difference! Matrix difference
  1399. degenerates to (= is the same as) matrix addition in a Boolean Algebra!!
  1400.  
  1401. =item *
  1402.  
  1403. C<$matrix1-E<gt>ExclusiveOr($matrix2,$matrix3);>
  1404.  
  1405. calculates the exclusive-or (which in the case of a Boolean Algebra happens
  1406. to be the same as the addition) of matrix2 and matrix3 and stores the
  1407. result in matrix1 (in-place is also possible)
  1408.  
  1409. =item *
  1410.  
  1411. C<$matrix1-E<gt>Complement($matrix2);>
  1412.  
  1413. calculates the complement of matrix2 and stores the result in matrix1
  1414. (in-place is also possible)
  1415.  
  1416. =item *
  1417.  
  1418. C<$boolean = $matrix1-E<gt>equal($matrix2);>
  1419.  
  1420. tests if matrix1 is the same as matrix2
  1421.  
  1422. =item *
  1423.  
  1424. C<$boolean = $matrix1-E<gt>subset($matrix2);>
  1425.  
  1426. tests if matrix1 is a subset of matrix2
  1427.  
  1428. =item *
  1429.  
  1430. C<$boolean = $matrix1-E<gt>inclusion($matrix2);>
  1431.  
  1432. alias for "subset()", deprecated
  1433.  
  1434. =item *
  1435.  
  1436. C<$boolean = $matrix1-E<gt>lexorder($matrix2);>
  1437.  
  1438. tests if matrix1 comes lexically before matrix2, i.e., if (matrix1 <= matrix2)
  1439. holds, as though the two bit vectors used to represent the two matrices were
  1440. two large numbers in binary representation
  1441.  
  1442. (Note that this is an B<arbitrary> order relationship!)
  1443.  
  1444. =item *
  1445.  
  1446. C<$result = $matrix1-E<gt>Compare($matrix2);>
  1447.  
  1448. lexically compares matrix1 and matrix2 and returns -1, 0 or 1 if
  1449. (matrix1 < matrix2), (matrix1 == matrix2) or (matrix1 > matrix2) holds,
  1450. respectively
  1451.  
  1452. (Again, the two bit vectors representing the two matrices are compared as
  1453. though they were two large numbers in binary representation)
  1454.  
  1455. =item *
  1456.  
  1457. C<$matrix1-E<gt>Copy($matrix2);>
  1458.  
  1459. copies the contents of matrix2 to an B<ALREADY EXISTING> matrix1
  1460.  
  1461. =item *
  1462.  
  1463. C<$new_matrix = $some_matrix-E<gt>Shadow();>
  1464.  
  1465. returns an object reference to a B<NEW> but B<EMPTY> matrix of
  1466. the B<SAME SIZE> as some_matrix
  1467.  
  1468. =item *
  1469.  
  1470. C<$twin_matrix = $some_matrix-E<gt>Clone();>
  1471.  
  1472. returns an object reference to a B<NEW> matrix of the B<SAME SIZE> as
  1473. some_matrix; the contents of some_matrix have B<ALREADY BEEN COPIED>
  1474. to the new matrix
  1475.  
  1476. =item *
  1477.  
  1478. B<Hint: method names all in lower case indicate a boolean return value!>
  1479.  
  1480. (Except for "C<new()>" and "C<new_from_string()>", of course!)
  1481.  
  1482. =back
  1483.  
  1484. Please refer to L<"OVERLOADED OPERATORS"> below for ways of using
  1485. overloaded operators instead of explicit method calls in order to
  1486. facilitate calculations with matrices!
  1487.  
  1488. =head1 DESCRIPTION
  1489.  
  1490. This class lets you dynamically create boolean matrices of arbitrary
  1491. size and perform all the basic operations for matrices on them, like
  1492.  
  1493. =over 4
  1494.  
  1495. =item -
  1496.  
  1497. setting or deleting elements,
  1498.  
  1499. =item -
  1500.  
  1501. testing wether a certain element is set,
  1502.  
  1503. =item -
  1504.  
  1505. computing the sum, difference, product, closure and complement of matrices,
  1506.  
  1507. (you can also compute the union, intersection, difference and exclusive-or
  1508. of the underlying bit vector)
  1509.  
  1510. =item -
  1511.  
  1512. copying matrices,
  1513.  
  1514. =item -
  1515.  
  1516. testing two matrices for equality or inclusion (subset relationship), and
  1517.  
  1518. =item -
  1519.  
  1520. computing the number of elements and the norm of a matrix.
  1521.  
  1522. =back
  1523.  
  1524. Please refer to L<"OVERLOADED OPERATORS"> below for ways of using
  1525. overloaded operators instead of explicit method calls in order to
  1526. facilitate calculations with matrices!
  1527.  
  1528. =head1 OVERLOADED OPERATORS
  1529.  
  1530. Calculations with matrices can not only be performed with explicit method
  1531. calls using this module, but also through "magical" overloaded arithmetic
  1532. and relational operators.
  1533.  
  1534. For instance, instead of writing
  1535.  
  1536.     $matrix1 = Math::MatrixBool->new($rows,$columns);
  1537.     $matrix2 = Math::MatrixBool->new($rows,$columns);
  1538.     $matrix3 = Math::MatrixBool->new($rows,$columns);
  1539.  
  1540.     [...]
  1541.  
  1542.     $matrix3->Multiplication($matrix1,$matrix2);
  1543.  
  1544. you can just say
  1545.  
  1546.     $matrix1 = Math::MatrixBool->new($rows,$columns);
  1547.     $matrix2 = Math::MatrixBool->new($rows,$columns);
  1548.  
  1549.     [...]
  1550.  
  1551.     $matrix3 = $matrix1 * $matrix2;
  1552.  
  1553. That's all!
  1554.  
  1555. Here is the list of all "magical" overloaded operators and their
  1556. semantics (meaning):
  1557.  
  1558. Unary operators: '-', '~', 'abs', testing, '!', '""'
  1559.  
  1560. Binary (arithmetic) operators: '+', '*', '|', '-', '&', '^'
  1561.  
  1562. Binary (relational) operators: '==', '!=', '<', '<=', '>', '>='
  1563.  
  1564. Binary (relational) operators: 'cmp', 'eq', 'ne', 'lt', 'le', 'gt', 'ge'
  1565.  
  1566. Note that both arguments to a binary operator from the list above must
  1567. be matrices; numbers or other types of data are not permitted as arguments
  1568. and will produce an error message.
  1569.  
  1570. =over 5
  1571.  
  1572. =item '-'
  1573.  
  1574. Unary Minus ( C<$matrix2 = -$matrix1;> )
  1575.  
  1576. Same as "Complement". See "Complement" below.
  1577.  
  1578. =item '~'
  1579.  
  1580. Complement ( C<$matrix2 = ~$matrix1;> )
  1581.  
  1582. The operator '~' (or unary '-') computes the complement of the given matrix.
  1583.  
  1584. =item abs
  1585.  
  1586. Absolute Value ( C<$no_of_elem = abs($matrix);> )
  1587.  
  1588. Here, the absolute value of a matrix has been defined as the number
  1589. of elements the given matrix contains. This is B<NOT> the same as the
  1590. "norm" of a matrix!
  1591.  
  1592. =item test
  1593.  
  1594. Boolean Test ( C<if ($matrix) { ... }> )
  1595.  
  1596. You can actually test a matrix as though it were a boolean value.
  1597.  
  1598. No special operator is needed for this; Perl automatically calls the
  1599. appropriate method in this package if "$matrix" is a blessed reference
  1600. to an object of the "Math::MatrixBool" class or one of its derived
  1601. classes.
  1602.  
  1603. This operation returns "true" (1) if the given matrix is not empty and
  1604. "false" ('') otherwise.
  1605.  
  1606. =item '!'
  1607.  
  1608. Negated Boolean Test ( C<if (! $matrix) { ... }> )
  1609.  
  1610. You can also perform a negated test on a matrix as though it were a boolean
  1611. value. For example:
  1612.  
  1613.     if (! $matrix) { ... }
  1614.  
  1615.     unless ($matrix) { ... }     #  internally, same as above!
  1616.  
  1617. This operation returns "true" (1) if the given matrix is empty and "false"
  1618. ('') otherwise.
  1619.  
  1620. =item '""""'
  1621.  
  1622. "Stringification" ( C<print "$matrix";> )
  1623.  
  1624. It is possible to get a string representation of a given matrix by just
  1625. putting the matrix object reference between double quotes.
  1626.  
  1627. Note that in general the string representation of a matrix will span over
  1628. multiple lines (i.e., the string which is generated contains "\n" characters,
  1629. one at the end of each row of the matrix).
  1630.  
  1631. Example:
  1632.  
  1633.     $matrix = new Math::MatrixBool(5,6);
  1634.     $matrix->One();
  1635.     print "$matrix";
  1636.  
  1637. This will print:
  1638.  
  1639.     [ 1 0 0 0 0 0 ]
  1640.     [ 0 1 0 0 0 0 ]
  1641.     [ 0 0 1 0 0 0 ]
  1642.     [ 0 0 0 1 0 0 ]
  1643.     [ 0 0 0 0 1 0 ]
  1644.  
  1645. =item '+'
  1646.  
  1647. Addition ( C<$matrix3 = $matrix1 + $matrix2;> )
  1648.  
  1649. The '+' operator calculates the sum of two matrices.
  1650.  
  1651. Examples:
  1652.  
  1653.     $all   =  $odd + $even;
  1654.  
  1655.     $all  +=  $odd;
  1656.     $all  +=  $even;
  1657.  
  1658. Note that the '++' operator will produce an error message if applied
  1659. to an object of this class because adding a number to a matrix makes
  1660. no sense.
  1661.  
  1662. =item '*'
  1663.  
  1664. Multiplication ( C<$matrix3 = $matrix1 * $matrix2;> )
  1665.  
  1666. The '*' operator calculates the matrix product of two matrices.
  1667.  
  1668. Examples:
  1669.  
  1670.     $test   =  $one * $one;
  1671.  
  1672.     $test  *=  $one;
  1673.     $test  *=  $test;
  1674.  
  1675. Note that you can use matrices of any size as long as their numbers of
  1676. rows and columns correspond in the following way (example):
  1677.  
  1678.         $matrix_3 = $matrix_1 * $matrix_2;
  1679.  
  1680.                           [ 2 2 ]
  1681.                           [ 2 2 ]
  1682.                           [ 2 2 ]
  1683.  
  1684.               [ 1 1 1 ]   [ 3 3 ]
  1685.               [ 1 1 1 ]   [ 3 3 ]
  1686.               [ 1 1 1 ]   [ 3 3 ]
  1687.               [ 1 1 1 ]   [ 3 3 ]
  1688.  
  1689. I.e., the number of columns of matrix #1 is the same as the number of
  1690. rows of matrix #2, and the number of rows and columns of the resulting
  1691. matrix #3 is determined by the number of rows of matrix #1 and the
  1692. number of columns of matrix #2, respectively.
  1693.  
  1694. This way you can also perform the multiplication of a matrix with a
  1695. vector, since a vector is just a degenerated matrix with several rows
  1696. but only one column, or just one row and several columns.
  1697.  
  1698. =item '|'
  1699.  
  1700. Union ( C<$matrix3 = $matrix1 | $matrix2;> )
  1701.  
  1702. The '|' operator is used to calculate the union of two matrices
  1703. (of corresponding elements).
  1704.  
  1705. Examples:
  1706.  
  1707.     $all   =  $odd | $even;
  1708.  
  1709.     $all  |=  $odd;
  1710.     $all  |=  $even;
  1711.  
  1712. =item '-'
  1713.  
  1714. Difference ( C<$matrix3 = $matrix1 - $matrix2;> )
  1715.  
  1716. The operator '-' calculates the (dotted) difference of two matrices, i.e.,
  1717.  
  1718.     0 - 0 == 0
  1719.     0 - 1 == 0
  1720.     1 - 0 == 1
  1721.     1 - 1 == 0
  1722.  
  1723. for each corresponding element.
  1724.  
  1725. Examples:
  1726.  
  1727.     $odd   =  $all  - $even;
  1728.  
  1729.     $all  -=  $even;
  1730.  
  1731. Note that the '--' operator will produce an error message if applied
  1732. to an object of this class because subtracting a number from a matrix
  1733. makes no sense.
  1734.  
  1735. =item '&'
  1736.  
  1737. Intersection ( C<$matrix3 = $matrix1 & $matrix2;> )
  1738.  
  1739. The '&' operator is used to calculate the intersection of two matrices
  1740. (of the corresponding elements).
  1741.  
  1742. Examples:
  1743.  
  1744.     $rest  =  $all & $even;
  1745.  
  1746.     $all  &=  $even;
  1747.  
  1748. =item '^'
  1749.  
  1750. ExclusiveOr ( C<$matrix3 = $matrix1 ^ $matrix2;> )
  1751.  
  1752. The '^' operator is used to calculate the exclusive-or of two matrices
  1753. (of their corresponding elements).
  1754.  
  1755. In fact this operation is identical with the addition of two matrices
  1756. in this case of a Boolean Algebra.
  1757.  
  1758. Examples:
  1759.  
  1760.     $odd   =  $all  ^ $even;
  1761.  
  1762.     $all  ^=  $even;
  1763.  
  1764. =item '=='
  1765.  
  1766. Test For Equality ( C<if ($matrix1 == $matrix2) { ... }> )
  1767.  
  1768. This operator tests two matrices for equality.
  1769.  
  1770. Note that B<without> operator overloading, C<( $matrix1 == $matrix2 )> would
  1771. test wether the two references B<pointed to> the B<same object>! (!)
  1772.  
  1773. B<With> operator overloading in effect, C<( $matrix1 == $matrix2 )> tests
  1774. wether the two matrix objects B<contain> exactly the B<same elements>!
  1775.  
  1776. =item '!='
  1777.  
  1778. Test For Non-Equality ( C<if ($matrix1 != $matrix2) { ... }> )
  1779.  
  1780. This operator tests wether two matrices are different.
  1781.  
  1782. Note again that this tests wether the B<contents> of the two matrices are
  1783. not the same, and B<not> wether the two B<references> are different!
  1784.  
  1785. =item 'E<lt>'
  1786.  
  1787. Test For True Subset ( C<if ($matrix1 E<lt> $matrix2) { ... }> )
  1788.  
  1789. This operator tests wether $matrix1 is a true subset of $matrix2, i.e.
  1790. wether the elements contained in $matrix1 are also contained in $matrix2,
  1791. but not all elements contained in $matrix2 are contained in $matrix1.
  1792.  
  1793. Example:
  1794.  
  1795.         [ 1 0 0 0 0 ]                       [ 1 0 0 0 1 ]
  1796.         [ 0 1 0 0 0 ]                       [ 0 1 0 0 0 ]
  1797.         [ 0 0 1 0 0 ]  is a true subset of  [ 0 0 1 0 0 ]
  1798.         [ 0 0 0 1 0 ]                       [ 0 0 0 1 0 ]
  1799.         [ 1 0 0 0 1 ]                       [ 1 0 0 0 1 ]
  1800.  
  1801.         [ 1 0 0 0 0 ]                       [ 1 0 0 0 1 ]
  1802.         [ 0 1 0 0 0 ]                       [ 0 1 0 0 0 ]
  1803.    but  [ 0 0 1 0 0 ]   is not a subset of  [ 0 0 1 0 0 ]
  1804.         [ 0 0 0 1 0 ]                       [ 0 0 0 1 0 ]
  1805.         [ 1 0 0 0 1 ]                       [ 0 0 0 0 1 ]
  1806.  
  1807. (nor vice-versa!)
  1808.  
  1809.         [ 1 0 0 0 1 ]                       [ 1 0 0 0 1 ]
  1810.         [ 0 1 0 0 0 ]                       [ 0 1 0 0 0 ]
  1811.    and  [ 0 0 1 0 0 ]     is a subset of    [ 0 0 1 0 0 ]
  1812.         [ 0 0 0 1 0 ]                       [ 0 0 0 1 0 ]
  1813.         [ 1 0 0 0 1 ]                       [ 1 0 0 0 1 ]
  1814.  
  1815. but not a true subset because the two matrices are identical.
  1816.  
  1817. =item 'E<lt>='
  1818.  
  1819. Test For Subset ( C<if ($matrix1 E<lt>= $matrix2) { ... }> )
  1820.  
  1821. This operator tests wether $matrix1 is a subset of $matrix2, i.e.
  1822. wether all elements contained in $matrix1 are also contained in $matrix2.
  1823.  
  1824. This also evaluates to "true" when the two matrices are the same.
  1825.  
  1826. =item 'E<gt>'
  1827.  
  1828. Test For True Superset ( C<if ($matrix1 E<gt> $matrix2) { ... }> )
  1829.  
  1830. This operator tests wether $matrix1 is a true superset of $matrix2, i.e.
  1831. wether all elements contained in $matrix2 are also contained in $matrix1,
  1832. but not all elements contained in $matrix1 are contained in $matrix2.
  1833.  
  1834. Note that C<($matrix1 E<gt> $matrix2)> is exactly the same as
  1835. C<($matrix2 E<lt> $matrix1)>.
  1836.  
  1837. =item 'E<gt>='
  1838.  
  1839. Test For Superset ( C<if ($matrix1 E<gt>= $matrix2) { ... }> )
  1840.  
  1841. This operator tests wether $matrix1 is a superset of $matrix2, i.e.
  1842. wether all elements contained in $matrix2 are also contained in $matrix1.
  1843.  
  1844. This also evaluates to "true" when the two matrices are equal.
  1845.  
  1846. Note that C<($matrix1 E<gt>= $matrix2)> is exactly the same as
  1847. C<($matrix2 E<lt>= $matrix1)>.
  1848.  
  1849. =item cmp
  1850.  
  1851. Compare ( C<$result = $matrix1 cmp $matrix2;> )
  1852.  
  1853. This operator compares the two matrices lexically, i.e. it regards the
  1854. two bit vectors representing the two matrices as two large (unsigned)
  1855. numbers in binary representation and returns "-1" if the number for
  1856. $matrix1 is smaller than that for $matrix2, "0" if the two numbers are
  1857. the same (i.e., when the two matrices are equal!) or "1" if the number
  1858. representing $matrix1 is larger than the number representing $matrix2.
  1859.  
  1860. Note that this comparison has nothing to do whatsoever with algebra,
  1861. it is just an B<arbitrary> order relationship!
  1862.  
  1863. It is only intended to provide an (arbitrary) order by which (for example)
  1864. an array of matrices can be sorted, for instance to find out quickly (using
  1865. binary search) if a specific matrix has already been produced before in some
  1866. matrix-producing process or not.
  1867.  
  1868. =item eq
  1869.  
  1870. "equal"
  1871.  
  1872. =item ne
  1873.  
  1874. "not equal"
  1875.  
  1876. =item lt
  1877.  
  1878. "less than"
  1879.  
  1880. =item le
  1881.  
  1882. "less than or equal"
  1883.  
  1884. =item gt
  1885.  
  1886. "greater than"
  1887.  
  1888. =item ge
  1889.  
  1890. "greater than or equal"
  1891.  
  1892. These are all operators derived from the "cmp" operator (see above).
  1893.  
  1894. They can be used instead of the "cmp" operator to make the intended
  1895. type of comparison more obvious in your code.
  1896.  
  1897. For instance, C<($matrix1 le $matrix2)> is much more readable and clearer
  1898. than C<(($matrix1 cmp $matrix2) E<lt>= 0)>!
  1899.  
  1900. =back
  1901.  
  1902. =head1 SEE ALSO
  1903.  
  1904. Bit::Vector(3), Math::MatrixReal(3), DFA::Kleene(3),
  1905. Math::Kleene(3), Set::IntegerFast(3), Set::IntegerRange(3).
  1906.  
  1907. =head1 VERSION
  1908.  
  1909. This man page documents "Math::MatrixBool" version 4.1.
  1910.  
  1911. =head1 AUTHOR
  1912.  
  1913. Steffen Beyer <sb@sdm.de>.
  1914.  
  1915. =head1 COPYRIGHT
  1916.  
  1917. Copyright (c) 1996, 1997 by Steffen Beyer. All rights reserved.
  1918.  
  1919. =head1 LICENSE AGREEMENT
  1920.  
  1921. This package is free software; you can redistribute it and/or
  1922. modify it under the same terms as Perl itself.
  1923.  
  1924.